/*
 * AbstractGraphImp.java
 *
 * Created on 2007年10月12日, 下午3:07
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */
package com.exclamation.util.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 *
 * @author littlerock
 */
public abstract class AbstractGraphImp implements GraphImp {

    protected ArrayList<Vertex> vs;
    protected ArrayList<Edge> es;
    protected boolean directed;

    protected AbstractGraphImp() {
        this(false, 0, 0);
    }

    protected AbstractGraphImp(boolean directed) {
        this(directed, 0, 0);
    }

    protected AbstractGraphImp(boolean directed, int vSize, int eSize) {
        this.directed = directed;
        if (vSize > 0) {
            vs = new ArrayList<Vertex>(vSize);
        } else {
            vs = new ArrayList<Vertex>();
        }

        if (eSize > 0) {
            es = new ArrayList<Edge>(eSize);
        } else {
            es = new ArrayList<Edge>();
        }
    }

    protected abstract Vertex creaeVertex(int id);

    protected abstract Edge createEdge(int id, int from, int to);

    public Vertex addVertex() {
        Vertex v = this.creaeVertex(this.vs.size() + 1);
        this.vs.add(v);
        return v;
    }

    public Edge addEdge(int from, int to) {
        if (this.getVertex(from) == null || this.getVertex(to) == null) {
            return null;
        }
        Edge e = this.createEdge(this.es.size() + 1, from, to);

        this.es.add(e);
        return e;
    }

    public Edge[] getEdges() {
        List<Edge> ne = new LinkedList<Edge>();
        for (Edge e : es) {
            if (e != null) {
                ne.add(e);
            }
        }
        Edge[] reVal = new Edge[ne.size()];
        return ne.toArray(reVal);
    }

    public Vertex[] getVertexes() {
        List<Vertex> nv = new LinkedList<Vertex>();
        for (Vertex v : vs) {
            if (v != null) {
                nv.add(v);
            }
        }
        Vertex[] reVal = new Vertex[nv.size()];
        return nv.toArray(reVal);
    }

    public boolean isDirected() {
        return this.directed;
    }

    public Edge getEdge(int e) {
        try {
            return this.es.get(e - 1);
        } catch (Exception ex) {
            return null;
        }
    }

    public Vertex getVertex(int v) {
        try {
            return this.vs.get(v - 1);
        } catch (Exception e) {
            return null;
        }
    }

    protected abstract void removeEdgeRelation(int e);

    protected abstract void removeVertexRelation(int v);

    public int removeEdge(int e) {
        if (this.getEdge(e) != null) {
            this.removeEdgeRelation(e);
            this.es.set(e - 1, null);
            return e;
        } else {
            return 0;
        }
    }

    public int removeVertex(int v) {
        if (this.getVertex(v) != null) {
            this.removeVertexRelation(v);
            Vertex vertex = this.getVertex(v);
            Edge[] edges = vertex.getEdges();
            for (Edge e : edges) {
                this.removeEdge(e.getId());
            }
            this.vs.set(v - 1, null);
            return v;
        } else {
            return 0;
        }
    }

    public void clear() {
        Vertex[] vertex = this.getVertexes();
        for (Vertex v : vertex) {
            this.removeVertex(v.getId());
        }
    }

    public Edge addEdge(int id, int from, int to) {
        if (id <= 0 || this.getVertex(from) == null || this.getVertex(to) == null || this.getEdge(id) != null) {
            return null;
        }
        if (id > this.es.size()) {
            es.ensureCapacity(id);
            for (int i = this.es.size() + 1; i < id; i++) {
                es.add(null);
            }
            return this.addEdge(from, to);
        } else {
            Edge e = this.createEdge(id, from, to);
            this.es.set(id - 1, e);
            return e;
        }
    }

    public Vertex addVertex(int id) {
        if (id <= 0 || this.getVertex(id) != null) {
            return null;
        }
        if (id > this.vs.size()) {
            vs.ensureCapacity(id);
            for (int i = this.vs.size() + 1; i < id; i++) {
                vs.add(null);
            }
            return this.addVertex();
        } else {
            Vertex v = this.creaeVertex(id);
            this.vs.set(id - 1, v);
            return v;
        }

    }

    public String toString() {
        StringBuffer buffer = new StringBuffer();

        buffer.append("Graph:");
        buffer.append("\n\tVertex:");
        for (Vertex v : getVertexes()) {
            buffer.append("\n\t" + v.getId());
            buffer.append("\n\t\tIn (");
            for (Edge e : v.getInEdges()) {
                buffer.append(e.getId() + " ");
            }
            buffer.append(")");
            buffer.append("\n\t\tOut (");
            for (Edge e : v.getOutEdges()) {
                buffer.append(e.getId() + " ");
            }
            buffer.append(")");
            buffer.append("\n\t\tAll (");
            for (Edge e : v.getEdges()) {
                buffer.append(e.getId() + " ");
            }
            buffer.append(")");
        }
        buffer.append("\n\tEdge:");
        for (Edge e : getEdges()) {
            buffer.append("\n\t" + e.getId() + "(" + e.getTail().getId() + ", " + e.getHead().getId() + ")");
        }
        return buffer.toString();
    }

    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }
        if (o instanceof Graph) {
            Graph g = (Graph) o;
            return this.toString().equals(g.toString());
        } else {
            return false;
        }
    }

    protected abstract GraphImp createNewGraphImp(boolean directed);

    public Object clone() {
        GraphImp newImp = this.createNewGraphImp(this.isDirected());
        return this.copyTo(newImp);
    }

    public Graph copyTo(GraphImp g) {
        return copy(this, g);
    }

    public Graph copyFrom(Graph g) {
        return copy(g, this);
    }

    public static Graph copy(Graph src, GraphImp dest) {
        if (src.isDirected() != dest.isDirected()) {
            return null;
        }
        dest.clear();
        Edge[] edges = src.getEdges();
        Vertex[] vertexes = src.getVertexes();

        for (int i = vertexes.length - 1; i >= 0; i--) {
            dest.addVertex(vertexes[i].getId()).setValue(vertexes[i].getValue());
        }

        for (int i = edges.length - 1; i >= 0; i--) {
            dest.addEdge(edges[i].getId(), edges[i].getTail().getId(), edges[i].getHead().getId()).setValue(edges[i].getValue());
        }

        return dest;
    }
}
